package main.java.indi.zyj.coderecord;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class PacificAtlantic {


    List<List<Integer>> res;
    boolean[][][] visited;
    int[][] pos = new int[][]{
            {0, 1},
            {1, 0},
            {0, -1},
            {-1, 0}
    };


    public List<List<Integer>> pacificAtlantic(int[][] heights) {

        int row = heights.length;
        int col = heights[0].length;
        res = new ArrayList<>();
        // 0是太平洋，1是大西洋如果可以访问到为true
        visited = new boolean[row][col][2];

        for (int i = 0; i < row; i++) {
            visited[i][0][0] = true;
            visited[i][col - 1][1] = true;
            dfs(heights, i, 0, 0);
            dfs(heights, i, col - 1, 1);
        }
        for (int i = 0; i < col; i++) {
            visited[0][i][0] = true;
            visited[row - 1][i][1] = true;
            dfs(heights, 0, i, 0);
            dfs(heights, row - 1, i, 1);
        }

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (visited[i][j][0] && visited[i][j][1]) {
                    res.add(new ArrayList<>(Arrays.asList(i, j)));
                }
            }
        }

        return res;

    }

    public void dfs(int[][] heights, int row, int col, int sign) {
        for (int i = 0; i < pos.length; i++) {
            int nextX = pos[i][0] + row;
            int nextY = pos[i][1] + col;
            if (nextX < 0 || nextX >= heights.length || nextY < 0 || nextY >= heights[0].length) {
                continue;
            }
            if (visited[nextX][nextY][sign] || heights[nextX][nextY] < heights[row][col]) {
                continue;
            }
            visited[nextX][nextY][sign] = true;
            dfs(heights, nextX, nextY, sign);
        }
    }


}
